package Offer211;

/**
 *  添加与搜索单词 - 数据结构设计
 *  请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * @author 23737
 * @time 2021.10.19
 */
public class Test {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        wordDictionary.addWord(".ad");
        wordDictionary.addWord("b..");
        System.out.println(wordDictionary.search("pad"));
        System.out.println(wordDictionary.search("bad"));
        System.out.println(wordDictionary.search(".ad"));
        System.out.println(wordDictionary.search("b.."));
    }
}

/**
 * 大神题解
 */
class WordDictionary {
    //声明一个根节点
    TrieNode root;
    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        //拷贝一个根节点
        TrieNode parentNode = root;
        //遍历
        for (int i = 0; i < word.length(); i++) {
            //查询当前字符为父节点的哪一个子节点
            int index = word.charAt(i) - 'a';
            //查询当前子节点是否存在,如果不存在就创建出来
            if(parentNode.children[index] == null){
                parentNode.children[index] = new TrieNode();
            }
            //更新父节点
            parentNode = parentNode.children[index];
        }
        //标记为末位节点
        parentNode.isWord = true;
    }

    public boolean search(String word) {
        return find(word,0,root);
    }

    private Boolean find(String word,int index,TrieNode node) {
        if(node == null) return false;
        if(index >= word.length()) return node.isWord;
        //得到当前节点字符
        char c = word.charAt(index);
        //判断是不是'.'
        if(c == '.'){
            for (int i = 0; i < 26; i++) {
                if(find(word,index+1,node.children[i]))
                    return true;
            }
            //如果找了一圈还么有找到 就代表找不到了
            return false;
        }else return find(word,index+1,node.children[c - 'a']);
    }

    class TrieNode {
        //定义节点类 使用数组对子节点进行模拟
        TrieNode[] children;
        // 标记是否是完整字符串
        boolean isWord;
        public TrieNode(){
            isWord = false; // 初始标记都不是终点
            children = new TrieNode[26]; //对应26个字符
        }
    }
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
